package com.benben.springSecurity.weiwei;

public class BestChufa {
    //暴力法
    class T {
        float max_val,min_val;
        String min_str,max_str;
    }
    public String optimalDivision1(int[] nums){
        T t = optimal(nums,0,nums.length-1,"");
        return t.max_str;
    }
    public T optimal(int[] nums,int start,int end,String res){
        T t = new T();
        if(start == end){
            t.max_val = nums[start];
            t.min_val = nums[start];
            t.max_str = "" + nums[start];
            t.min_str = "" + nums[start];
            return t;
        }
        t.min_val = Float.MAX_VALUE;
        t.max_val = Float.MIN_VALUE;
        t.min_str = t.max_str = "";
        for(int i=start;i<end;i++){
            T left = optimal(nums,start,i,"");
            T right = optimal(nums,i+1,end,"");
            if(t.min_val > left.min_val / right.max_val){
                t.min_val = left.min_val / right.max_val;
                t.min_str = left.min_str + "/" + (i+1 != end ? "(" : "") + right.max_val + (i+1 != end ? ")" : "");
            }
            if(t.max_val < left.max_val / right.min_val) {
                t.max_val = left.max_val / right.min_val;
                t.max_str = left.max_str + "/" + (i+1 != end ? "(":"") + right.min_val + (i+1 != end?")":"");
            }
        }
        return t;
    }
    //数学法：通过数学公式推导，最优解永远是a/(b/c/d/e/..)
    public String optimalDivision2(int[] nums){
        if(nums.length ==1){
            return nums[0]+"";
        }
        if(nums.length == 2){
            return nums[0] + "/" + nums[1];
        }
        StringBuilder res = new StringBuilder(nums[0]+"/(" + nums[1]);
        for(int i=2;i<nums.length;i++){
            res.append("/"+nums[i]);
        }
        res.append(")");
        return res.toString();
    }
}
